using System;

namespace Arbol
{

	public class TotalSupportTree : AssocRuleMining
	{

		/* ------ FIELDS ------ */

		// Data structures    
		/// <summary>
		/// The reference to start of t-tree. </summary>
		protected internal TtreeNode[] startTtreeRef;

		// Diagnostics 
		/// <summary>
		/// The number of frequent sets (nodes in t-tree with above minimum 
		/// support) generated so far. 
		/// </summary>
		protected internal int numFrequentsets = 0;
		/// <summary>
		/// The number of updates required to generate the T-tree. </summary>
		protected internal long numUpdates = 0l;
		/// <summary>
		/// Time to generate T-tree. </summary>
		protected internal string duration = null;

		/* ------ CONSTRUCTORS ------ */

		/// <summary>
		/// Processes command line arguments. </summary>
        public TotalSupportTree()            
        {
        }
		public TotalSupportTree(string[] args) : base(args)
		{
		}

		/* ------ METHODS ------ */

		/* ---------------------------------------------------------------- */
		/*                                                                  */
		/*                           ADD TO T-TREE                          */
		/*                                                                  */
		/* ---------------------------------------------------------------- */

		/* ADD TO T-TREE */

		/// <summary>
		/// Commences process of adding an itemset (with its support value) to a
		/// T-tree when using a T-tree either as a storage mechanism, or when adding to 
		/// an existing T-tree. </summary>
		/// <param name="itemSet"> The given itemset. Listed in numeric order (not reverse
		/// numeric order!). </param>
		/// <param name="support"> The support value associated with the given itemset.  </param>

		public virtual void addToTtree(short[] itemSet, int support)
		{
			// Determine index of last elemnt in itemSet.
		int endIndex = itemSet.Length - 1;

		// Add itemSet to T-tree.
			startTtreeRef = addToTtree(startTtreeRef,numOneItemSets + 1, endIndex,itemSet,support);
		}

		/* ADD TO T-TREE */

		/// <summary>
		/// Inserts a node into a T-tree. <P> Recursive procedure. </summary>
		/// <param name="linkRef"> the reference to the current array in Ttree. </param>
		/// <param name="size"> the size of the current array in T-tree. </param>
		/// <param name="endIndex"> the index of the last element/attribute in the itemset, 
		/// which is also used as a level counter. </param>
		/// <param name="itemSet"> the given itemset. </param>
		/// <param name="support"> the support value associated with the given itemset. </param>
		/// <returns> the reference to the revised sub-branch of t-tree.  </returns>

		protected internal virtual TtreeNode[] addToTtree(TtreeNode[] linkRef, int size, int endIndex, short[] itemSet, int support)
		{
		// If no array describing current level in the T-tree or T-tree
		// sub-branch create one with "null" nodes.	
		if (linkRef == null)
		{
			linkRef = new TtreeNode[size];
			for (int index = 1;index < linkRef.Length;index++)
			{
				linkRef[index] = null;
			}
		}

		// If null node at index of array describing current level in T-tree 
		// (T-tree sub-branch) create a T-tree node describing the current 
		// itemset sofar.
		int currentAttribute = itemSet[endIndex];
		if (linkRef[currentAttribute] == null)
		{
					linkRef[currentAttribute] = new TtreeNode();
		}

		// If at right level add support 	
		if (endIndex == 0)
		{
			linkRef[currentAttribute].support = linkRef[currentAttribute].support + support;
			return (linkRef);
		}

		// Otherwise proceed down branch and return	
		linkRef[currentAttribute].childRef = addToTtree(linkRef[currentAttribute].childRef, currentAttribute,endIndex - 1,itemSet,support);
		// Return
		return (linkRef);
		}

		/*---------------------------------------------------------------------- */
		/*                                                                       */
		/*                        T-TREE SEARCH METHODS                          */
		/*                                                                       */
		/*---------------------------------------------------------------------- */

		/* GET SUPPORT FOT ITEM SET IN T-TREE */

		/// <summary>
		/// Commences process for finding the support value for the given item set
		/// in the T-tree (which is know to exist in the T-tree). <P> Used when
		/// generating Association Rules (ARs). Note that itemsets are stored in
		/// reverse order in the T-tree therefore the given itemset must be processed
		/// in reverse. </summary>
		/// <param name="itemSet"> the given itemset. </param>
		/// <returns> returns the support value (0 if not found).  </returns>

		protected internal virtual int getSupportForItemSetInTtree(short[] itemSet)
		{
		int endInd = itemSet.Length - 1;

			// Last element of itemset in Ttree (Note: Ttree itemsets stored in
		// reverse)
		  if (startTtreeRef[itemSet[endInd]] != null)
		  {
			// If "current index" is 0, then this is the last element (i.e the
			// input is a 1 itemset)  and therefore item set found
			if (endInd == 0)
			{
				return (startTtreeRef[itemSet[0]].support);
			}
			// Otherwise continue down branch
			else
			{
				TtreeNode[] tempRef = startTtreeRef[itemSet[endInd]].childRef;
				if (tempRef != null)
				{
					return (getSupForIsetInTtree2(itemSet, endInd - 1,tempRef));
				}
				// No further branch therefore rerurn 0
			else
			{
				return (0);
			}
			}
		  }
		// Item set not in Ttree thererfore return 0
			else
			{
				return (0);
			}
		}

		/// <summary>
		/// Returns the support value for the given itemset if found in the T-tree
		/// and 0 otherwise. <P> Operates recursively. </summary>
		/// <param name="itemSet"> the given itemset. </param>
		/// <param name="index"> the current index in the given itemset. </param>
		/// <param name="linRef"> the reference to the current T-tree level. </param>
		/// <returns> returns the support value (0 if not found).  </returns>

		private int getSupForIsetInTtree2(short[] itemSet, int index, TtreeNode[] linkRef)
		{
			// Element at "index" in item set exists in Ttree
		  if (linkRef[itemSet[index]] != null)
		  {
			  // If "current index" is 0, then this is the last element of the
			// item set and therefore item set found
			if (index == 0)
			{
				return (linkRef[itemSet[0]].support);
			}
			// Otherwise continue provided there is a child branch to follow
			else if (linkRef[itemSet[index]].childRef != null)
			{
							  return (getSupForIsetInTtree2(itemSet,index - 1, linkRef[itemSet[index]].childRef));
			}
			else
			{
				return (0);
			}
		  }
		// Item set not in Ttree therefore return 0
		else
		{
			return (0);
		}
		}

		/*----------------------------------------------------------------------- */
		/*                                                                        */
		/*                    ASSOCIATION RULE (AR) GENERATION                    */
		/*                                                                        */
		/*----------------------------------------------------------------------- */

		/* GENERATE ASSOCIATION RULES */

		/// <summary>
		/// Initiates process of generating Association Rules (ARs) from a
		/// T-tree. 
		/// </summary>

		public virtual void generateARs()
		{
		// Command line interface output
		Console.WriteLine("GENERATE ARs:\n-------------");

		// Set rule data structure to null
		startRulelist = null;

		// Generate
		generateARs2();
		}

		/// <summary>
		/// Loops through top level of T-tree as part of the AR generation
		/// process. 
		/// </summary>

		protected internal virtual void generateARs2()
		{
		// Loop
		for (int index = 1;index <= numOneItemSets;index++)
		{
			if (startTtreeRef[index] != null)
			{
				if (startTtreeRef[index].support >= minSupport)
				{
					short[] itemSetSoFar = new short[1];
				itemSetSoFar[0] = (short) index;
				generateARs(itemSetSoFar,index, startTtreeRef[index].childRef);
				}
			}
		}
		}

		/* GENERATE ASSOCIATION RULES */

		/// <summary>
		/// Continues process of generating association rules from a T-tree by
		/// recursively looping through T-tree level by level. </summary>
		/// <param name="itemSetSofar"> the label for a T-tree node as generated sofar. </param>
		/// <param name="size"> the length/size of the current array lavel in the T-tree. </param>
		/// <param name="linkRef"> the reference to the current array level in the T-tree.  </param>

		protected internal virtual void generateARs(short[] itemSetSofar, int size, TtreeNode[] linkRef)
		{

		// If no more nodes return
		if (linkRef == null)
		{
			return;
		}

		// Otherwise process
		for (int index = 1; index < size; index++)
		{
			if (linkRef[index] != null)
			{
				if (linkRef[index].support >= minSupport)
				{
				// Temp itemset
				short[] tempItemSet = realloc2(itemSetSofar,(short) index);
				// Generate ARs for current large itemset
				generateARsFromItemset(tempItemSet,linkRef[index].support);
					// Continue generation process
				generateARs(tempItemSet,index,linkRef[index].childRef);
				}
			}
		}
		}

		/* GENERATE ASSOCIATION RULES */

		/// <summary>
		/// Generates all association rules for a given large item set found in a
		/// T-tree structure. <P> Called from <TT>generateARs</TT> method. </summary>
		/// <param name="itemSet"> the given large itemset. </param>
		/// <param name="support"> the associated support value for the given large itemset.  </param>

		private void generateARsFromItemset(short[] itemSet, double support)
		{
			// Determine combinations
		short[][] combinations2 = combinations(itemSet);

		// Loop through combinations
		for (int index = 0;index < combinations2.Length;index++)
		{
				// Find complement of combination in given itemSet
			short[] complement2 = complement(combinations2[index],itemSet);
			// If complement is not empty generate rule
			if (complement2 != null)
			{
				double confidenceForAR = getConfidence(combinations2[index], support);
			if (confidenceForAR >= confidence)
			{
				   insertRuleintoRulelist(combinations2[index], complement2,confidenceForAR);
			}
			}
		}
		}

		/*----------------------------------------------------------------------- */
		/*                                                                        */
		/*                                GET METHODS                             */
		/*                                                                        */
		/*----------------------------------------------------------------------- */

		/* GET CONFIDENCE */

		/// <summary>
		/// Calculates and returns the confidence for an AR given the antecedent
		/// item set and the support for the total item set. </summary>
		/// <param name="antecedent"> the antecedent (LHS) of the AR. </param>
		/// <param name="support"> the support for the large itemset from which the AR is
		/// generated. </param>
		/// <returns> the associated confidence value (as a precentage) correct to two 
		/// decimal places.  </returns>

		protected internal virtual double getConfidence(short[] antecedent, double support)
		{
			// Get support for antecedent
			double supportForAntecedent = (double) getSupportForItemSetInTtree(antecedent);

		// Return confidence
		double confidenceForAR = ((double) support / supportForAntecedent) * 10000;
		int tempConf = (int) confidenceForAR;
		confidenceForAR = (double) tempConf / 100;
		return (confidenceForAR);
		}

		/*----------------------------------------------------------------------- */
		/*                                                                        */
		/*                              UTILITY METHODS                           */
		/*                                                                        */
		/*----------------------------------------------------------------------- */

		/* SET NUMBER ONE ITEM SETS */

		/// <summary>
		/// Sets the number of one item sets field (<TT>numOneItemSets</TT> to 
		/// the number of supported one item sets. 
		/// </summary>

		public virtual void setNumOneItemSets()
		{
			numOneItemSets = NumSupOneItemSets;
		}

		/*----------------------------------------------------------------------- */
		/*                                                                        */
		/*                              OUTPUT METHODS                            */
		/*                                                                        */
		/*----------------------------------------------------------------------- */

		/* ---------------- */
		/*   OUTPUT T-TRRE  */
		/* ---------------- */

		/// <summary>
		/// Commences process of outputting T-tree structure contents to screen. </summary>
		public virtual void outputTtree()
		{
		int number = 1;

		// Loop

		for (short index = 1; index < startTtreeRef.Length; index++)
		{
			if (startTtreeRef[index] != null)
			{
				string itemSetSofar = (new short?(reconvertItem(index))).ToString();
				Console.Write("[" + number + "] {" + itemSetSofar);
				Console.WriteLine("} = " + startTtreeRef[index].support);
				outputTtree((new int?(number)).ToString(),itemSetSofar, startTtreeRef[index].childRef);
			number++;
			}
		}
		}

		/// <summary>
		/// Continue process of outputting T-tree. <P> Operates in a recursive 
		/// manner. </summary>
		/// <param name="number"> the ID number of a particular node. </param>
		/// <param name="itemSetSofar"> the label for a T-tree node as generated sofar. </param>
		/// <param name="linkRef"> the reference to the current array level in the T-tree.  </param>

		private void outputTtree(string number, string itemSetSofar, TtreeNode[] linkRef)
		{
		// Set output local variables.
		int num = 1;
		number = number + ".";
		itemSetSofar = itemSetSofar + " ";

		// Check for empty branch/sub-branch.
		if (linkRef == null)
		{
			return;
		}

		// Loop through current level of branch/sub-branch.
		for (short index = 1;index < linkRef.Length;index++)
		{
			if (linkRef[index] != null)
			{
				string newItemSet = itemSetSofar + (reconvertItem(index));
				Console.Write("[" + number + num + "] {" + newItemSet);
				Console.WriteLine("} = " + linkRef[index].support);
				outputTtree(number + num,newItemSet,linkRef[index].childRef);
				num++;
			}
		}
		}

		/* ----------------------- */
		/*   OUTPUT FREQUENT SETS  */
		/* ----------------------- */
		/// <summary>
		/// Commences the process of outputting the frequent sets contained in
		/// the T-tree. 
		/// </summary>

		public virtual void outputFrequentSets()
		{
		int number = 1;

		Console.WriteLine("FREQUENT (LARGE) ITEM SETS:\n" + "---------------------------");
		Console.WriteLine("Format: [N] {I} = S, where N is a sequential " + "number, I is the item set and S the support.");

		// Loop

		for (short index = 1; index <= numOneItemSets; index++)
		{
			if (startTtreeRef[index] != null)
			{
				if (startTtreeRef[index].support >= minSupport)
				{
					string itemSetSofar = (new short?(reconvertItem(index))).ToString();
					Console.WriteLine("[" + number + "] {" + itemSetSofar + "} = " + startTtreeRef[index].support);
					number = outputFrequentSets(number + 1,itemSetSofar, index,startTtreeRef[index].childRef);
				}
			}
		}

		// End

		Console.WriteLine("\n");
		}

		/// <summary>
		/// Outputs T-tree frequent sets. <P> Operates in a recursive manner. </summary>
		/// <param name="number"> the number of frequent sets so far. </param>
		/// <param name="itemSetSofar"> the label for a T-treenode as generated sofar. </param>
		/// <param name="size"> the length/size of the current array level in the T-tree. </param>
		/// <param name="linkRef"> the reference to the current array level in the T-tree. </param>
		/// <returns> the incremented (possibly) number the number of frequent sets so
		/// far.  </returns>

		private int outputFrequentSets(int number, string itemSetSofar, int size, TtreeNode[] linkRef)
		{

		// No more nodes

		if (linkRef == null)
		{
			return (number);
		}

		// Otherwise process

		itemSetSofar = itemSetSofar + " ";
		for (short index = 1; index < size; index++)
		{
			if (linkRef[index] != null)
			{
				if (linkRef[index].support >= minSupport)
				{
					string newItemSet = itemSetSofar + (reconvertItem(index));
				Console.WriteLine("[" + number + "] {" + newItemSet + "} = " + linkRef[index].support);
					number = outputFrequentSets(number + 1,newItemSet,index, linkRef[index].childRef);
				}
			}
		}

		// Return

		return (number);
		}

		/* ------------------------------ */
		/*   OUTPUT NUMBER FREQUENT SETS  */
		/* ------------------------------ */
		/// <summary>
		/// Commences the process of counting and outputing number of supported
		/// nodes in the T-tree.<P> A supported set is assumed to be a non null node in
		/// the T-tree. 
		/// </summary>

		public virtual void outputNumFreqSets()
		{

		// If empty tree (i.e. no supported sets) do nothing
		if (startTtreeRef == null)
		{
			Console.WriteLine("Number of frequent " + "sets = 0");
		}
		// Otherwise count and output
		else
		{
			Console.WriteLine("Number of frequent sets = " + countNumFreqSets());
		}
		}

		/* COUNT NUMBER OF FRQUENT SETS */
		/// <summary>
		/// Commences process of counting the number of frequent (large/supported
		/// sets contained in the T-tree. 
		/// </summary>

		protected internal virtual int countNumFreqSets()
		{
			// If empty tree return 0
		if (startTtreeRef == null)
		{
			return (0);
		}

		// Otherwise loop through T-tree starting with top level
		int num = 0;
		for (int index = 1; index <= numOneItemSets; index++)
		{
			// Check for null valued top level Ttree node.
			if (startTtreeRef[index] != null)
			{
				if (startTtreeRef[index].support >= minSupport)
				{
				num = countNumFreqSets(index, startTtreeRef[index].childRef,num + 1);
				}
			}
		}

		// Return
		return (num);
		}

		/// <summary>
		/// Counts the number of supported nodes in a sub branch of the T-tree. </summary>
		/// <param name="size"> the length/size of the current array level in the T-tree. </param>
		/// <param name="linkRef"> the reference to the current array level in the T-tree. </param>
		/// <param name="num"> the number of frequent sets sofar.  </param>

		protected internal virtual int countNumFreqSets(int size, TtreeNode[] linkRef, int num)
		{

		if (linkRef == null)
		{
			return (num);
		}

		for (int index = 1; index < size; index++)
		{
			if (linkRef[index] != null)
			{
				if (linkRef[index].support >= minSupport)
				{
								num = countNumFreqSets(index, linkRef[index].childRef,num + 1);
				}
			}
		}

		// Return

		return (num);
		}

		/* --------------------------- */
		/*   OUTPUT T-TREE STATISTICS  */
		/* --------------------------- */
		/// <summary>
		/// Commences the process of outputting T-tree statistics (for diagnostic
		/// purposes): (a) Storage, (b) Number of nodes on P-tree, (c) number of
		/// partial support increments (updates) and (d) generation time. 
		/// </summary>

		public virtual void outputTtreeStats()
		{
			Console.WriteLine("T-TREE STATISTICS\n-----------------");
		Console.WriteLine(calculateStorage() + " (Bytes) storage");
		Console.WriteLine(TtreeNode.NumberOfNodes + " nodes");
		Console.WriteLine(countNumFreqSets() + " frequent sets");
		Console.WriteLine(numUpdates + " support value increments");
		Console.WriteLine(duration);
		}

		/* --------------------------- */
		/*   OUTPUT NUMBER OF UPDATES  */
		/* --------------------------- */
		/// <summary>
		/// Commences the process of determining and outputting the storage
		/// requirements (in bytes) for the T-tree 
		/// </summary>
		/// <summary>
		/// Outputs the number of update and number of nodes created during the
		/// generation of the T-tree (the later is not the same as the number of 
		/// supported nodes). 
		/// </summary>

		public virtual void outputNumUpdates()
		{
		Console.WriteLine("Number of Nodes created = " + TtreeNode.NumberOfNodes);
		Console.WriteLine("Number of Updates       = " + numUpdates);
		}

		/* ----------------- */
		/*  OUTPUT STORAGE   */
		/* ----------------- */
		/// <summary>
		/// Commences the process of determining and outputting the storage
		/// requirements (in bytes) for the T-tree. <P> Example: Given ---
		/// <PRE>
		///    	{1,2,3} 
		///		{1,2,3}
		/// {1,2,3}
		///		{1,2,3}
		/// {1,2,3}
		/// </PRE>
		/// This will produce a T-tree as shown below:	
		/// <PRE>
		/// +---+---+---+---+ 		
		/// | 0 | 1 | 2 | 3 |	
		/// +---+---+---+---+
		///      |   |   |
		///   |   |   +-----------+
		///   |   |               |
		///   |   +---+         +---+---+---+    
		///      |       |         | 0 | 1 | 2 |
		/// ( 5 )   +---+---+   +---+---+---+
		/// (nul)   | 0 | 1 |         |   |
		///     +---+---+         |   +----+
		///    |           |        |
		///    |           |      +---+---+
		///  ( 5 )         |      | 0 + 1 |
		///  (nul)       ( 5 )    +---+---+
		///                     (nul)          |
		///               |
		///	     ( 5 )
		///	     (nul)    
		/// </PRE>					     
		/// 0 elements require 4 bytes of storage, null nodes (not shown above) 4 bytes 
		/// of storage, others 12 bytes of storage.			
		/// </summary>

		public virtual void outputStorage()
		{

		// If empty tree (i.e. no supported sets) do nothing
		if (startTtreeRef == null)
		{
			return;
		}

		/* Otherwise calculate storage */
		Console.WriteLine("T-tree Storage          = " + calculateStorage() + " (Bytes)");
		}

		/* CALCULATE STORAGE */
		/// <summary>
		/// Commences process of calculating storage requirements for  T-tree. </summary>

		protected internal virtual int calculateStorage()
		{
			// If emtpy tree (i.e. no supported sets) return 0
		if (startTtreeRef == null)
		{
			return (0);
		}

		/* Step through top level */	
		int storage = 4; // For element 0
		for (int index = 1; index <= numOneItemSets; index++)
		{
			if (startTtreeRef[index] != null)
			{
				storage = storage + 12 + calculateStorage(0,startTtreeRef[index].childRef);
			}
			else
			{
				storage = storage+4;
			}
		}
		// Return
		return (storage);
		}

		/// <summary>
		/// Calculate storage requirements for a sub-branch of the T-tree. </summary>
		/// <param name="localStorage"> the storage as calculated sofar (set to 0 at start). </param>
		/// <param name="linkRef"> the reference to the current sub-branch of the T-tree.  </param>

		private int calculateStorage(int localStorage, TtreeNode[] linkRef)
		{

		if (linkRef == null)
		{
			return (0);
		}

		for (int index = 1; index < linkRef.Length; index++)
		{
			if (linkRef[index] != null)
			{
				localStorage = localStorage + 12 + calculateStorage(0,linkRef[index].childRef);
			}
			else
			{
				localStorage = localStorage + 4;
			}
		}

		 /* Return */

		 return (localStorage+4); // For element 0
		}
	}




}